# Definition for singly-linked list.
class ListNode:
    def __init__(self, x, next=None):
        self.val = x
        self.next = next

    def output(self, limit = 100):
        print(self.val, end='')
        if limit == 0:
            print('E')
            return 
        if self.next:
            print(' -> ', end='')
            self.next.output(limit-1)
        else:
            print('')
    
    def printval(self, name):
        print(name + ': ' + str(self.val)) 

class Solution:
    def _reverseGroup(self, ihead, head, tail) -> (ListNode, ListNode):
        # tail.printval('tail')
        if head == tail:
            tail.next = ihead
            return
        new_head = head.next
        # new_head.printval('new_head')
        head.next = ihead
        self._reverseGroup(head, new_head, tail)

    def kStep(self, head: ListNode, k) -> ListNode:
        if k == 0 or head is None:
            return head
        if head.next:
            return self.kStep(head.next, k-1)
        return None

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if k <= 1:
            return head
        reshead = ListNode(233)
        res = reshead
        while True:
            tail = self.kStep(head, k-1)
            if tail is None:
                res.next = head
                break
            # tail.output(5)
            next_head = tail.next
            self._reverseGroup(head, head.next, tail)
            # tail.output(5)
            res.next = tail
            res = head
            head = next_head
        return reshead.next


if __name__ == "__main__":
    s = Solution()
    l1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    s.reverseKGroup(l1, 2).output(5)
    l2 = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    s.reverseKGroup(l2, 3).output(5)
    s.reverseKGroup(ListNode(1, ListNode(2)), 2).output()